package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         174,
		Discription: "公主救骑士",
		Level:       3,
		Labels: map[string]int{
			"动态规划": 1,
			"无后效性": 1,
		},
	})
}

/*
无后效性：当前的选择不会堆之后的计算造成影响
*/
func CalculateMinimumHP(dungeon [][]int) int {
	m := len(dungeon)
	n := len(dungeon[0])

	//minHealth从该节点出发到达公主需要的最小初始生命值
	minHealth := make([][]int, m)
	for i := range minHealth {
		minHealth[i] = make([]int, n)
	}

	//初始的生命值要+1
	minHealth[m-1][n-1] = max(1, -dungeon[m-1][n-1]+1)
	for i := m - 2; i >= 0; i-- {
		minHealth[i][n-1] = max(1, minHealth[i+1][n-1]-dungeon[i][n-1])
	}

	for j := n - 2; j >= 0; j-- {
		minHealth[m-1][j] = max(1, minHealth[m-1][j+1]-dungeon[m-1][j])
	}

	for i := m - 2; i >= 0; i-- {
		for j := n - 2; j >= 0; j-- {
			minHealth[i][j] = max(1, min(minHealth[i+1][j], minHealth[i][j+1])-dungeon[i][j])
		}
	}

	return minHealth[0][0]
}
